package LeetCode;

import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}14:32
 */
public class LeetCode51 {
    private static List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        List<Integer> row = new ArrayList<>();

        boolean[] col = new boolean[n];
        //左对角线
        boolean[] dia1 = new boolean[2 * n - 1];
        //右对角线
        boolean[] dia2 = new boolean[2 * n - 1];
        putQueen(n,0,row,col,dia1,dia2);
        return res;
    }

    /**
     *
     * @param n 几皇后
     * @param index 第几行
     * @param row 行结果集
     */
    public void putQueen(int n, int index, List<Integer> row,boolean[] col,boolean[] dia1,boolean[] dia2){
        if ( index == n){
            res.add(generateBoard(n, row));
            return;
        }

        // i是第几列
        for (int i = 0; i < n; i++){
            //尝试将第index行的皇后放在第i行
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
                row.add(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n,index + 1,row,col,dia1,dia2);
                //回溯
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
                row.remove(row.size() - 1);
            }
        }
    }

    private List<String > generateBoard(int n, List<Integer> row) {
        if (row.size() == n){
            List<String> board = new ArrayList<>();
            //初始化点
            String[][] boardReslut = new String[n][n];
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++) {
                    if (j == row.get(i)) {
                        boardReslut[i][j] = "Q";
                    } else {
                        boardReslut[i][j] = ".";
                    }
                }
                builder.append(Arrays.toString(boardReslut[i]));

            }
            board.add(builder.toString());
            return board;
        }else {
            return null;
        }
    }

    public static void main(String[] args) {
        new LeetCode51().solveNQueens(4);
        System.out.println(res.toString());;
    }
}
